The field of invention is block chain technology, and specifically in the area of mining algorithms and mining devices. Bitcoin and Cryptocurrencies that derived from it are based on a unique combination of a proof of work block chain, a peer-to-peer network, and a cryptographically validated ledger. This invention is an improvement on the proof of work block chain portion of the prior art. This improvement also enables some features in the other two components.
Block Chains and Mining
For the purpose of this invention a proof of work block chain is a data structure consisting of a series of “blocks” that are progressively derived from the previous block in the chain or a specific ‘genesis block.’ The process of mining is the discovery and assembly of these new blocks. First information from the peer-to-peer network a miner is connected to is retrieved and the preliminary data in the block is calculated. Next some other data fields are searched via a ‘brute force’ method to find a set of values that makes the block as a whole pass a fitness function. This fitness function is designed to keep the level of computational effort needed to discover an acceptable block high while the effort needed to verify the data values are acceptably mined low. This brute force process is sometimes referred to as the “puzzle,” “computational puzzle,” or “client puzzle” in academic literature, or as “hashing” or “mining” in practitioner literature.
Each block of a block chain contains data that conforms to one of three characterizations. The first data characterization is a reference to previous data in the block chain. The second characterization is data that is payload and bookkeeping data values. The final data characterization is nonce data. The reference to previous data is typically a cryptographic hash of the block just prior to the current block. The payload and bookkeeping values vary based on the specific block chain, but include values such as the hash of the current ledger entries, the time the block was generated as reported by the miner, and factors influencing the application of the fitness function. The nonce is a data value that is present principally to impact the fitness function and to insure each block is unique. Typical implementations of the nonce is derived from a process described in the field as “mining.” The nonce of a block is an unrelated data field that is progressively altered by the miners until the application of a fitness function determine that the block is acceptable for use as a previous block. Typical nonce update strategies are incrementing/decrementing the nonce value by a fixed amount, a deterministic walk of the range of the nonce values controlled by some function, and a random change of the nonce value. Once an acceptable value is found the block being mined is broadcast to the other members of the peer-to-peer network and generally the miners begin the creation of a new block. There are typically multiple nonce values that cause the block to be found fit by the fitness function, but the ratio of acceptable to unacceptable values is very high, from millions to billions to octillions or more. The effort to find these rare acceptable values serves as the “proof of work.”
For the original bitcoin block chain the fitness function is to calculate the SHA256 hash of the block, convert the hash to an integer number, and then compare the number to another number kept in the bookkeeping data in the block header. If the converted hash value is less than the converted difficulty value then the block is acceptable. Higher difficulty required that a smaller converted hash value be found. The easiest possible hash for the easiest possible difficulty occurred in approximately one in 2^32 hashes (over 4 billion). Modern difficulties can require more than 2^64 hashes, or over 16 quintillion calculations (16,000,000,000,000,000,000). There fitness function for bitcoin also included a regularly occurring recalculation of the difficulty to ensure that a block was found, on average, every 10 minutes. This value makes up part of the bookkeeping data.
After a while “altcoins” emerged. These are other block chains that are usually derived from bitcoin code and protocols. Some altcoins changed this fitness function while others would alter the parameters of the difficulty adjustment or the frequency of block generation. One way the fitness function would be altered would be to replace the hashing function with other hashing functions like Scrypt, Blake, SHA3, and in some instances multiple functions. In some cases the stated goal for altering the fitness function would make developing custom hardware to mine the block chain very difficult. Some altcoins moved their fitness function away from a hash calculation and replaced it with a fitness function that integrated the peer-to-peer network and cryptographic ledger to form a “proof of stake” system where the computers that controlled certain sums of their altcoin would be responsible for creating the blocks on the block chains. The proof of stake systems require participation in the ledger system. In other words everyone mining in the system must have control over some of the currency in the system and thus a “stake” or interest in the viability of the payload.
The content of the block chain has also evolved over time. Bitcoin was designed to be a distributed ledger of tokens denominated in the eponymous units of bitcoin. These tokens have been used as a digital replacement for cash and currency in many instances. The block chain was used as a settlement mechanism to fight against “double spend” attacks and other such fraud attempts against the cryptographic ledger that the peer-to-peer network was distributing.
The mining process simultaneously protected the ledger via proof of work (as described later) as well as served as the creation mechanism for the bitcoin currency tokens. According to the validation rules the first transaction in a block is a special transaction that can output up to a fixed amount of bitcoins based on a predetermined schedule and the amount of unspent bitcoins in the transactions referenced in the block. The miner for that block is responsible for generating that special transaction and determines where the output bitcoin tokens go. Typically, they will provide an address representing themselves or the other entities mining this block. Some miners will sell those tokens to pay for the expenses related to mining.
Much like altcoins the payload of these block chains have evolved from a cryptographic ledger to include more complex items. Some consumers encode data representing other tokens into their ledger transactions or other completely unrelated data, such as poems and pictures. Some other block chains allow for more complex entries such as multi-token ledgers, “proof of existence” hashes, computer code, and smart contracts.
The ultimate incentive in mining is to decide what content is placed into the payload. So long as the content of the payload conforms to the rules established by each block chain each miner has wide discretion to decide what does and does not get included in each block that they mine.
Purpose of Proof of Work in a Block Chain
The original purpose of proof of work, as used in Hashcash (Back, A., Hashcash), is to require some minimal expenditure of computational power on the part of a sender in order for a mail recipient to consider an email message to not be junk. By applying an increased level of effort it was hoped that junk mail senders could not send millions of duplicate emails because they either lack the computation resources to calculate the millions of hashes or the cost of electricity and hardware maintenance would make the effort of spam to become economically infeasible.
The block chain as used by bitcoin, however, uses the proof of work as an anti-fraud measure to prevent the historical ledger from being re-written by malicious parties. In order to re-write a ledger entry at some point in the block chain's history you would also need to re-calculate the hashes and nonces of all blocks that were generated after the block was added to the block chain. The older the entry, the more blocks there are that would need to be re-mined. This is where the proof of work is valuable. Bitcoin also makes this proof of work more difficult by distributing the proof of work effort across a peer-to-peer network. Rather than each node working on separate block chains there is (ideally) one block chain being calculated across the entire network. So the net power of the whole peer-to-peer network is focusing on creating the next block to follow what is considered to be the current best block.
Since the creation of a previous block used what is assumed to be all of the computational power available to the peer-to-peer network then if you could redirect all of the hashing power used to create it you would need approximately the same amount of time tore-write history for that block as it took to generate the block in the first place. And to change one block you would also, by necessity, need to regenerate all blocks that followed it so it would be the best block. So to rewrite a ledger entry that was part of a block that has since had 10 hours of blocks generated after it, then it would take approximately 10 hours to regenerate just the blocks that have been added on to the block chain it came from, assuming you could re-direct all the computational power to the generation. So if computational power were kept constant and control of hashing power were not considered, the anti-fraud nature of the block chain derives from the characteristic that rewriting history takes just as long to do as generating the history in the first place.
The computational power does not stay constant on the block and redirecting the entire network to re-write history is nearly impossible because the bitcoin protocol incentivizes individual miners to work on the current longest chain for personal profit. The incentive structure is designed to inhibit the malicious rewriting of history when all miners are “honest.” It would take the cooperation of about half of the computational power on the peer-to-peer network to allow rewriting of even the most current block, and thus destabilize the history of the block chain. In literature this is referred to as a “51% attack.” This incentive has resulted in a diverse set of competing miners across many legal jurisdictions.
The amount of mining occurring on any block chain is also highly variable, and almost always increasing for any viable block chains. The rules for the payload and the bookkeeping are generally known so that can be easily verified, and from that information new blocks can be generated by anyone with enough computational power. And computational power can continually being created and added to the peer-to-peer network. This is considered by the community to be a feature of the protocol, not a problem.
However, if a miner kept enough “dark” computational power (not generally know to the network because it isn't reporting mined blocks) that was in excess of the computational power of the existing network it could run a “time warp” attack where large portions of the ledger history is re-written. Because of the incentive structure of most block chains this would tend to destabilize the block chains it was run against once these time-warped blocks are propagated across the network. The fungible nature of some of these fitness functions is why it is possible for large amounts of computational power to be used in these attacks if one were to spend enough energy and resources on computing equipment.